The present disclosure relates generally to determining similarities between graphs, and more particularly, to building soft correspondence between node sets of respective input graphs.
Many real-world, complex objects with structural properties can be modeled as graphs. For example, the World Wide Web can be represented as a graph with web-pages as nodes and hyperlinks as edges. In another example, a patient's medical data can be modeled as a symptom-lab test graph, which can be constructed from his/her medical records, providing an indicator of the structure information of possible disease s/he carries (e.g., the association between a particular symptom and some lab test, the co-occurrence of different symptom).
Random walk graph kernel has been used as a tool for various data mining tasks including classification and similarity computation. Despite its usefulness, however, it suffers from its expensive computational costs which are at least O(n3) or O(m2) for graphs with n nodes and m edges.